class Solution:
    def maxScoreSightseeingPair(self, A: list) -> int:
        scores = [0 for _ in range(len(A))]
        cur = -2**31
        for i in range(len(A) - 1, 0, -1):
            score = A[i] - i
            scores[i] = max(cur, score)
            cur = scores[i]
        res = 0
        for i in range(len(A) - 1):
            res = max(res, A[i] + i + scores[i + 1])
        return res
